/**
 * Copyright (C), 2018-2018
 * FileName: quickSort  * Author:   lcsos
 * Date:     2018/10/11 21:26
 * Description:
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.qdu.study.arithmetic.first;

import java.util.Arrays;

/**
 * 〈一句话功能简述 〉<br>
 *  快速排序
 *
 * 1、先选定队列中，某一个元素为基数Value（一般选择头元素，或尾元素）。
 *
 * 2、将基数Value依次与所有元素比较大小。按照比较结果将元素分为两个队列A、B。
 * 一个所有元素比基数Value大，一个所有元素比基数Value小。
 *
 * 3、将A作为新的队列，再次选定基数，然后分成两个更小的队列
 *
 * 4、就这样一直将每一个小的队列无限的拆分成更小的两个队列。
 *
 * 5、一直到一个队列已经拆分成不能拆封为止（也就是一个元素）
 *
 * 6、因为队列之间的顺序都是固定的。将这些队列一次组合起来，整体的排序就算完成了。
 *
 * 注意这里有两个最核心的步骤，就是
 *
 * 1、选出Value元素，将整体队列划分成两个子队列
 *
 * 2、然后将子队列重新作为一个新的，整体规模比当前要小的，新的队列，进行计算，直到计
 * 算起来非常容易为止。
 *
 * 这两个核心步骤造就了快排天生的优势：
 *
 * 1、通过比较大小划分到子队列中的元素，在未来的比较过程中，这个元素的比较范围始终都停
 * 留在这个子队列中，不再做多余的比较。这使得早期的比较对后期的比较仍然有很大的影响。而
 * 类似于冒泡的排序方法，则前期很多的比较，对后期的作用非常小。这点和kmp算法很像，前期的
 * 比较尽量做到最大的利用。
 *
 * 2、将原有规模的队列，拆分成若干个规模小的子队列，这些子队列要解决的问题与原有队列一致
 * ，只是规模变小了。这样不断的拆分，形成一种分而治之的思想。这种思想与背包算法也是不谋而合。
 *
 * @author Lcs
 * @create 2018/10/11 
 * @since 1.0.0
 */

public class quickSort {

    private static int quickSort1(int[] arr,int start,int end){
        //选取数组的第一个数作为中轴 例如3 6 7 1 2 0 8 , 中轴为3
        int middleValue = arr[start];
        //start是数组第一个数，end是数组最后一个数
        while (start < end){
            //从数组右边往左查询第一个比中轴小的数，为arr[end]
            while (arr[end] >= middleValue && start < end){
                end--;
            }
        //比中轴小的记录移到低端 0 6 7 1 2 0 8
            arr[start] = arr[end];
            //从数组左边往右边查询第一个比中轴大的数，为arr[start]
            while (arr[start] <= middleValue && start < end){
                start++;
            }
        //比中轴大的记录移到高端 0 6 7 1 2 6 8
            arr[end] = arr[start];

        }
        //中轴记录到刚才移动的位置 0 3 7 1 2 6 8
        arr[start] = middleValue;
        //返回中轴位置,此时为1
        return start;
    }

    private static void quickSort2(int[] arr,int start,int end){

        if (start >= end){
            return;
        }
        //将list数组进行一分为二
        int middleIndex = quickSort1(arr,start,end);
        //对低字表进行递归排序
        quickSort2(arr,start,middleIndex - 1);
        //对高字表进行递归排序
        quickSort2(arr,middleIndex + 1,end);
    }

    private static void quickSort3(int[] arr){
        //对数组进行配置
        quickSort2(arr,0,arr.length - 1);
    }

    public static void main(String[] args) {
        //设置一个数组
        int[] arr = new int[]{ 1, 12, 2, 13, 3, 14, 4, 15, 5, 16, 17, 17, 177, 18, 8, 8, 19};
        //传递数组,进行排序
        quickSort3(arr);
        //返回排序结果
        System.out.println(Arrays.toString(arr));
    }


}
